package com.zy.drug.controller;




public class BinaryTreeFromPreInorder {

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }

        private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
            if (preStart > preEnd || inStart > inEnd) {
                return null;
            }

            // 创建当前子树的根节点，根据先序遍历的第一个元素
            TreeNode root = new TreeNode(preorder[preStart]);

            // 在中序遍历中找到根节点的位置
            int rootIndexInorder = 0;
            for (int i = inStart; i <= inEnd; i++) {
                if (inorder[i] == root.val) {
                    rootIndexInorder = i;
                    break;
                }
            }

            // 确定左子树和右子树的节点数
            int leftSubtreeSize = rootIndexInorder - inStart;

            // 递归构建左子树和右子树
            root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, rootIndexInorder - 1);
            root.right = buildTreeHelper(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, rootIndexInorder + 1, inEnd);

            return root;
        }

        // 测试方法
        public static void main(String[] args) {
            BinaryTreeFromPreInorder builder = new BinaryTreeFromPreInorder();
            int[] preorder = {3, 9, 20, 15, 7};
            int[] inorder = {9, 3, 15, 20, 7};
            TreeNode root = builder.buildTree(preorder, inorder);

            // 验证树的结构，例如通过层序遍历打印节点值
            // 这里省略了验证代码，你可以根据需要添加
        }
    }

